package g

/*
 * @lc app=leetcode.cn id=17 lang=golang
 *
 * [17] 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。
1-		  2-abc     3-def
4-ghi     5-jkl    6-mno
7-pqrs    8-tuv    9-wxyz
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
*/

// @lc code=start
func letterCombinations(digits string) []string {
	// return letterCombinations1(digits)
	return letterCombinationsRecursion(digits)
}

// 遍历
func letterCombinations1(digits string) []string {
	if len(digits) == 0 {
		return nil
	}
	num2strs := map[byte][]byte{
		'2': {'a', 'b', 'c'},
		'3': {'d', 'e', 'f'},
		'4': {'g', 'h', 'i'},
		'5': {'j', 'k', 'l'},
		'6': {'m', 'n', 'o'},
		'7': {'p', 'q', 'r', 's'},
		'8': {'t', 'u', 'v'},
		'9': {'w', 'x', 'y', 'z'},
	}
	var results []string
	if len(digits) == 1 {
		x := num2strs[digits[0]]
		for i := 0; i < len(x); i++ {
			results = append(results, string([]byte{x[i]}))
		}
	} else if len(digits) == 2 {
		x := num2strs[digits[0]]
		y := num2strs[digits[1]]
		for i := 0; i < len(x); i++ {
			for j := 0; j < len(y); j++ {
				results = append(results, string([]byte{x[i], y[j]}))
			}
		}
	} else if len(digits) == 3 {
		x := num2strs[digits[0]]
		y := num2strs[digits[1]]
		z := num2strs[digits[2]]
		for i := 0; i < len(x); i++ {
			for j := 0; j < len(y); j++ {
				for k := 0; k < len(z); k++ {
					results = append(results, string([]byte{x[i], y[j], z[k]}))
				}
			}
		}
	} else if len(digits) == 4 {
		x := num2strs[digits[0]]
		y := num2strs[digits[1]]
		z := num2strs[digits[2]]
		a := num2strs[digits[3]]
		for i := 0; i < len(x); i++ {
			for j := 0; j < len(y); j++ {
				for k := 0; k < len(z); k++ {
					for l := 0; l < len(a); l++ {
						results = append(results, string([]byte{x[i], y[j], z[k], a[l]}))
					}
				}
			}
		}
	}

	return results
}

// 遍历
func letterCombinationsRecursion(digits string) []string {
	if len(digits) == 0 {
		return nil
	}
	num2strs := map[byte][]string{
		'1': {},
		'2': {"a", "b", "c"},
		'3': {"d", "e", "f"},
		'4': {"g", "h", "i"},
		'5': {"j", "k", "l"},
		'6': {"m", "n", "o"},
		'7': {"p", "q", "r", "s"},
		'8': {"t", "u", "v"},
		'9': {"w", "x", "y", "z"},
	}
	num2strs['1'] = num2strs[digits[0]]
	digits = digits[1:]
	for len(digits) > 0 {
		num2strs['1'] = combination(num2strs['1'], num2strs[digits[0]])
		digits = digits[1:]
	}
	tmp := num2strs['1']
	return tmp
}

func combination(a, b []string) []string {
	var results []string
	for i := 0; i < len(a); i++ {
		for j := 0; j < len(b); j++ {
			results = append(results, a[i]+b[j])
		}
	}
	return results
}

// @lc code=end
